package com.sfx.数据结构.哈希表;

/**
 * 1. 什么是哈希算法 ?
 * 哈希算法也叫散列算法/摘要算法,就是可以将任意长度的数据编程固定长度数据的过程,这个固定长度的数据就是hash值
 * hash算法将任意对象,分配一个编号的过程,编号就是一个有限范围的数字(比如是int范围内)
 * 2. JDK生成hashcode
 * jdk生成的hashcode是由Object类的hashcode方法来实现的.不同的对象的hashcode不同
 * 3. String生成的hashcode
 * String的hashcode覆盖了Object的父类的hashcode
 * public int hashCode() {
 * int h = hash;
 * if (h == 0 && value.length > 0) {
 * char val[] = value;
 * for (int i = 0; i < value.length; i++) {
 * h = 31 * h + val[i];
 * h = (h<<5) - h + val[i];
 * }
 * hash = h;
 * }
 * return h;
 * }
 * 我们一般选择 乘以质数,hash冲突的概率更低
 * 4. murmurHash
 * 第二代哈希算法,是一种非加密的哈希函数
 *  1) : 计算速度快
 *  2) : 碰撞率低,处理一亿个数据最多只有两个冲突
 *  3) : 能够很好地保持数据的随机性.
 * 5. 我们的代码使用了尾插法,如果改成头插法呢 ?
 *  头插法,多线程情况下发送死循环.
 * 6. JDK的HashMap中采用了讲对象hashCode高低位相互异或的方式减少冲突,怎么理解呢 ?
 *
 *
 * 7. 我们的HashTable中表格容量是2的n次方,很多优化都是基于这个前提,能否不同2的n次方容量呢 ?
 *
 * 8. JDK的 HashMap在链表长度过长会转化为红黑树,你怎么看呢 ?
 *
 */
class MyHashMap {

    private Entry[] table = new Entry[16];//make sure size is powers of 2;
    private int size = 0;
    private final float loadFactor = 0.75f;
    private final int threshold = (int) (loadFactor * table.length);

    static class Entry {
        int key;
        int val;
        Entry next;

        public Entry(int key, int val) {
            this.key = key;
            this.val = val;
        }

        public Entry() {
        }
    }

    public void put(int key, int val) {
        //计算新的索引
        int index = getIndex(key);
        if (table[index] == null) {
            table[index] = new Entry(key, val);
        } else {
            //如果再次添加相同的key,那么就需要覆盖val
            Entry h1 = table[index];
            while (h1 != null) {
                if (h1.key == key) {
                    h1.val = val;
                    return;
                }
                if (h1.next == null) {
                    break;
                }
                h1 = h1.next;
            }
            h1.next = new Entry(key, val);
        }
        if (++size > threshold) {
            // 进行扩容
            resize();
        }
    }

    public int get(int key) {
        //得到key的val
        int index = getIndex(key);
        Entry head = table[index];
        if (head == null) {
            return -1;
        } else {
            Entry cur = head;
            while (cur != null) {
                if (cur.key == key) {
                    return cur.val;
                }
                cur = cur.next;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int index = getIndex(key);
        Entry head = table[index];
        if (head == null) {//not found
            return;
        } else {
            Entry cur = head;
            Entry prev = null;
            while (cur != null) {
                if (cur.key == key) {
                    if (prev == null) table[index] = cur.next;
                    else prev.next = cur.next;
                    size--;
                    return;
                } else {
                    prev = cur;
                    cur = cur.next;
                }
            }
        }
    }

    private void resize() {
        //double size
        Entry[] newTable = new Entry[table.length << 1];
        // 1.会遍历旧的table,然后将按照 &1是否等于0拆分成两个链表
        for (int i = 0; i < table.length; ++i) {
            Entry p = table[i];// 得到链表头结点
            if (p != null) {
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null) {
                    if ((p.key & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p;
                    }
                    p = p.next;
                }
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
    }

    //make sure size is powers of 2
    //then key%size = key&(size-1)
    private int getIndex(int key) {
        return key & (table.length - 1);
    }
}